package algorithm.leetcode.I1to100;

public class Q5 {

    public String longestPalindrome(String s) {
        if (s.length() == 1) return s;

        int begin = 0, end = 0;

        // dp二维数组表示从i到j是否为回文串
        // 状态转移方程 dp[i][j]=dp[i+1][j-1] && s[i]==s[j], 即i到j之间的字符串是否为回文由该串去掉两头是回文且两头相等
        // 初始状态:当j-i=0时肯定为true,当j-i=1时比较i和j,
        boolean[][] dp = new boolean[s.length()][s.length()];
        // 先纵列
        for (int j = 0; j < dp.length; j++) {
            // 再横向,从下往上
            for (int i = j; i >= 0; i--) {
                if (i == j) dp[i][j] = true;
                else if (j-i == 1) dp[i][j] = s.charAt(i) == s.charAt(j);
                else dp[i][j] = dp[i+1][j-1] && s.charAt(i) == s.charAt(j);

                if (dp[i][j] && j-i+1 > end-begin) {
                    begin = i;
                    end = j;
                }
            }
        }

        return s.substring(begin, end+1);
    }

    public static void main(String[] args) {
        Q5 five = new Q5();
        System.out.println(five.longestPalindrome("babad"));
    }

}
